package org.hot100.h034;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: wjy
 * @Date: 2021/12/13 14:20
 */
public class Solution {

    public static void main(String[] args) {

        //int[] ints = {5, 7, 7, 8, 8, 8, 8, 8, 9, 10};
        //int[] ints = {1};
        int[] ints = {1, 2, 2, 3, 4, 4, 4};

        Solution solution = new Solution();
        int[] res = solution.searchRange2(ints, 4);

        for (int i : res) {
            System.out.println(i);
        }

    }

    // 双指针法 执行用时：1ms 击败13.61%的用户 内存消耗：41.4MB 击败80.79%的用户
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[]{-1, -1};
        }

        int start = 0, end = nums.length - 1;
        boolean flag1 = false, flag2 = false;

        for (int i = 0, j = nums.length - 1; i <= j && j >= 0;) {
            if (nums[i] == target) {
                start = i;
                flag1 = true;
            } else {
                i++;
            }
            if (nums[j] == target) {
                end = j;
                flag2 = true;
            } else {
                j--;
            }
            if (flag1 && flag2) {
                return new int[]{start, end};
            }
        }

        return new int[]{-1, -1};
    }

    // 二分查找法 执行用时：0ms 击败100.00%的用户 内存消耗：41.3MB 击败91.21%的用户
    public int[] searchRange2(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[]{-1, -1};
        }

        int left = 0, right = nums.length, mid = -1;

        // 寻找第一个target下标
        while (left < right) {
            mid = (left + right) / 2;
            if (target <= nums[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }

        }

        int l = 0, r = nums.length;

        // 寻找第一个大于target的值的下标
        while (l < r) {
            mid = (l + r) / 2;

            if (target + 1 <= nums[mid]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        // nums[left] != target 检查target是否存在于数组中
        if (left == nums.length || nums[left] != target) {
            return new int[]{-1, -1};
        }
        return new int[]{left, l - 1};
    }

}
